﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<ctype.h>
#include<assert.h>
#include<stdbool.h>
//合并两个有序数组
//给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目
//请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列
//注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n
//示例 1：
//输入：nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3
//输出：[1, 2, 2, 3, 5, 6]
//解释：需要合并[1, 2, 3] 和[2, 5, 6] 。
//合并结果是[1, 2, 2, 3, 5, 6] ，其中斜体加粗标注的为 nums1 中的元素。
//示例 2：
//输入：nums1 = [1], m = 1, nums2 = [], n = 0
//输出：[1]
//解释：需要合并[1] 和[] 。
//合并结果是[1] 。
//示例 3：
//输入：nums1 = [0], m = 0, nums2 = [1], n = 1
//输出：[1]
//解释：需要合并的数组是[] 和[1] 。
//合并结果是[1] 。
//注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中

//void merge(int* nums1, int nums1size, int m, int* nums2, int nums2size, int n)
//{
//	int l1 = m - 1;
//	int l2 = n - 1;
//	int l3 = m + n - 1;
//	while (l1 >= 0 && l2 >= 0)//只要有一个条件为假就跳出循环
//	{
//		if (nums1[l1] < nums2[l2])
//		{
//			nums1[l3--] = nums2[l2--];
//		}
//		else
//		{
//			nums1[l3--] = nums1[l1--];
//		}
//	}
//	//出了循环有两种情况：l1 < 0 或者 l2 < 0
//	//只需要处理一种情况：l2 <=0(说明l2中的数据还没有完全放入到nums1中)
//	while (l2 >= 0)
//	{
//		nums1[l3--] = nums2[l2--];
//	}
// }
//此时nums1中包含了nums2中的数据，nums1是升序数组

//顺序表的问题及思考
//1.中间 / 头部的插⼊删除，时间复杂度为O(N)  涉及移动数据
//2.增容需要申请新空间，拷⻉数据，释放旧空间。会有不⼩的消耗。
//3.增容⼀般是呈2倍的增⻓，势必会有⼀定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插⼊了5个数据，后⾯没有数据插⼊了，那么就浪费了95个数据空间。
//思考：如何解决以上问题呢？

//针对顺序表：中间/头部插入效率低下，增容降低运行效率，增容造成空间浪费   --------链表

//链表的概念及结构
//概念：链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的

//节点的组成主要有两个部分：当前节点要保存的数据和保存下⼀个节点的地址（指针变量）。
//图中指针变量plist保存的是第⼀个节点的地址，我们称plist此时“指向”第⼀个节点，如果我们希
//望plist“指向”第⼆个节点时，只需要修改plist保存的内容为0x0012FFA0。
//链表中每个节点都是独⽴申请的（即需要插⼊数据时才去申请⼀块节点的空间），我们需要通过指针变量来保存下⼀个节点位置才能从当前节点找到下⼀个节点。

//假设当前保存的节点为整型：
//struct SListNode
//{
//	int data; //节点数据 
//	struct SListNode* next; //指针变量⽤保存下⼀个节点的地址 
//};
//当我们想要保存⼀个整型数据时，实际是向操作系统申请了⼀块内存，这个内存不仅要保存整型数据，也需要保存下⼀个节点的地址（当下⼀个节点为空时保存的地址为空）。
//当我们想要从第⼀个节点⾛到最后⼀个节点时，只需要在前⼀个节点拿上下⼀个节点的地址（下⼀个节点的钥匙）就可以了。


































































